package com.fanshuai.algorithms.dynamic;

import java.util.ArrayList;
import java.util.List;

public class Charactor {

    /**
     * 设A和B是2个字符串，要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：
     (1)删除一个字符(delete)；
     (2)插入一个字符(insert)；
     (3)将一个字符改为另一个字符(substitute)。

     动态规划求解：
     dp table: dp[i][j]表示s1[1..i]和s2[1..j]子串的编辑距离。字符串索引从1开始计数
     状态转移方程：
     dp[i][j] = if (s1[i] == s2[j]) {
     dp[i-1][j-1]  //当前位置字符相等，指针往前移
     } else {
        //当前位置指针不相等
        min(
            dp[i-1][j-1] + 1, //字符替换，i,j指针往前移
            dp[i-1][j] + 1, //字符删除,i指针往前移
            dp[i][j-1] + 1, //字符插入,j指针往前移
        )
     }

     badcase:
     dp[0][0] = 0
     dp[i][0] = i  //删除i个字符
     dp[0][j] = j  //删除j个字符
     * @param s1
     * @param s2
     * @return
     */
    public static List<Edit> editDistance(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];

        /**
         * 根据bad case确定dp table边界
         */
        dp[0][0] = 0;
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = i; //删除i个字符
        }
        for (int j = 1; j < len2; j++) {
            dp[0][j] = j; //插入j个字符
        }

        /**
         * 根据状态转移方程，按一定遍历顺序求取dp table
         * 状态转移方程求取最值，有不同的选择
         */
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                char c1 = s1.charAt(i - 1);
                char c2 = s2.charAt(j - 1);

                if (c1 == c2) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    int a1 = dp[i-1][j-1] + 1; //替换
                    int a2 = dp[i-1][j] + 1;//删除
                    int a3 = dp[i][j-1] + 1;//插入

                    int choose = getMin(a1, a2, a3);
                    if (choose == 1) {
                        dp[i][j] = a1;
                    } else if (choose == 2) {
                        dp[i][j] = a2;
                    } else if (choose == 3) {
                        dp[i][j] = a3;
                    } else {
                        System.out.println("impossible");
                    }
                }
            }
        }

        /**
         * 从dp[m][n]回溯，直到dp[0][0]，找到最优解经过的路径
         * 根据状态转移方程做不同的选择，回退指针
         */
        List<Edit> list = new ArrayList<>();

        int m = len1, n = len2;
        while (m > 0 && n > 0) {
            char c1 = s1.charAt(m - 1);
            char c2 = s2.charAt(n - 1);
            if (c1 == c2) {
                //什么都不做
                m--;
                n--;
            } else {
                int a1 = dp[m-1][n-1] + 1; //替换
                int a2 = dp[m-1][n] + 1;//删除
                int a3 = dp[m][n-1] + 1;//插入

                int choose = getMin(a1, a2, a3);
                if (choose == 1) {//替换
                    Edit edit = new Edit(m - 1, 1);
                    list.add(edit);
                    m--;
                    n--;
                } else if (choose == 2) {//删除
                    Edit edit = new Edit(m - 1, 3);
                    list.add(edit);
                    m--;
                } else if (choose == 3) {//插入
                    Edit edit = new Edit(m - 1, 2);
                    list.add(edit);
                    n--;
                } else {
                    System.out.println("impossible here");
                }
            }
        }

        while (m > 0) { //删除
            Edit edit = new Edit(m - 1, 3);
            list.add(edit);
            m--;
        }
        while (n > 0) { //插入
            Edit edit = new Edit(0, 2);
            list.add(edit);
            n--;
        }

        return list;
    }

    private static int getMin(int a1, int a2, int a3) {
        int i = 0;

        int min = Integer.MAX_VALUE;
        if (a1 < min) {
            min = a1;
            i = 1;
        }
        if (a2 < min) {
            i = 2;
        }
        if (a3 < min) {
            i = 3;
        }
        return i;
    }

    public static class Edit {
        public int index;
        public int op;  //操作  0-什么都不做  1--替换  2--插入  3--删除

        public Edit(int index, int op) {
            this.index = index;
            this.op = op;
        }

        @Override
        public String toString() {
            return "Edit{" +
                    "index=" + index +
                    ", op=" + op +
                    '}';
        }
    }

    /**
     * 最长回文字符串 "aba", "abcba", "ainonia", "abba"为回文子串
     * dp table: dp[i][j]表示s[i..j]是否为回文子串  0<=i<s.len, i<=j<s.len
     * 状态转移方程：
     * dp[i][j] = if (s[i] == s[j]) {
     *     j == i + 1 || dp[i+1][j-1]
     * } else {
     *     false
     * }
     *
     * bad case: j<i dp[i][j]=false (j<i时，s[i..j]为空字符串,dp[i][j]=0)
     *           j=i dp[i][j]=true 单个字符串为回文子串，长度为1
     * @param s
     * @return
     */
    public static String cycleSubString(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        long maxLen = 0;
        int start = 0;
        int end = 0;
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                char c1 = s.charAt(i);
                char c2 = s.charAt(j);

                if (c1 == c2) {
                    if (j == i + 1) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                } else {
                    dp[i][j] = false;
                }
                //记录最长回文子串
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    start = i;
                    end = j;
                }
            }
        }

        return s.substring(start, end + 1);
    }

    public static void main(String[] args) {
        String s = cycleSubString("abccbahhasdfgfdsarhgifg");
        //System.out.println(s);

        String s1 = "aabbc";
        String s2 = "ccaahhbb";
        List<Edit> list = editDistance(s1, s2);
        System.out.println(list);
    }
}
